package 使用最小花费爬楼梯;

import java.util.Arrays;
import java.util.StringJoiner;

/**
 * @author: AirMan
 * @date: 2025/4/29 11:01
 * @description:
 */
public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 重叠子问题 ==> 如果让前面的步骤都是花费最少的
        // Dynamic-Programming
        // ① dp数组及其下标的含义：dp[i]表示爬到第i层所需要最少花费
        // ② 状态转移方程：dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])
        // ③ dp数组初始化：dp[1] = [0], dp[2] = 0;
        // ④ 确定遍历顺序：从楼层的下面往上遍历，利用下面楼层的信息然后往上爬
        // ⑤ 举例推导dp数组：如果 cost 为 [1,100,1,1,1,100,1,1,100,1]
        //                    ==> dp为：0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6(11层)

        if (cost.length < 2) {
            return 0;
        }
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = 0;
        // print
    /*  System.out.println(Arrays.toString(cost));
        StringJoiner sb = new StringJoiner(",");
        sb.add("0");
        sb.add("0");
        System.out.println(sb.toString());
    */
        for (int i = 2; i <= cost.length; i++) {
            int curLevCost = Math.min(dp[0] + cost[i - 2], dp[1] + cost[i - 1]);
//            sb.add(curLevCost + "");
            dp[0] = dp[1];
            dp[1] = curLevCost;
//            System.out.println(sb);
        }

        return dp[1];
    }
}
